package com.sort;

import java.util.Arrays;

/*
* 快速排序
*       时间复杂度：最好情况： O(n logn)；最坏情况O(n²) 平均 O(n logn)
* */
public class quick_sort {
    public static void main(String[] args) {
        int[] arr = {2,3,1,4,54,3};
        new quick_sort().quivkSort(arr);

    }

    public void quivkSort(int[] arr){
        int[] copy = Arrays.copyOf(arr, arr.length);
        sort(copy,0,arr.length-1);
        System.out.println(Arrays.toString(copy));;
    }

    public void sort(int[] arr,int left,int right ){

        if (left < right){
            int pvIndex = s(arr, left, right);
            sort(arr,left,pvIndex-1);
            sort(arr,pvIndex+1,right);
        }
    }

    public int s(int[] arr, int left, int right){
        int pv = arr[right];
        int i = left;
        for (int j = i; j < right; j++) {
            if (arr[j] < pv){
                swap(arr,j,i);
                i++;
            }
        }
        swap(arr,i,right);

        return i;
    }




    public void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a [j];
        a[j] = temp;
    }
}
